package com.gupao.alg.alg1;

import java.util.Arrays;

public class Topic1_MergeKArray {
    /**
     * K 个数组合并问题
     * 解决的问题：
     * 实现先将各个数组拼接到一起，然后再排序，从而实现有序排序
     * @param args
     */
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 6};
        int[] arr2 = {1, 2, 5, 7};
        int[] arr3 = {3, 6, 9, 11};
        int[] arr4 = {5, 7, 13, 17};
        //这其实就是归并的基本思想
        int[] merge1 = merge2Array(arr1, arr2);
        int[] merge2 = merge2Array(arr3, arr4);
        int[] merge = merge2Array(merge1, merge2);
//        System.out.println(Arrays.toString(merge));

        //方式2：先合并到一起再排序
        int[][] twoArray2 = new int[4][4];
        twoArray2[0] = Arrays.copyOf(arr1, 4);
        twoArray2[1] = Arrays.copyOf(arr2, 4);
        twoArray2[2] = Arrays.copyOf(arr3, 4);
        twoArray2[3] = Arrays.copyOf(arr4, 4);
        int[] a = mergeArrays(twoArray2);
        System.out.println(Arrays.toString(a));

    }

    public static int[] merge2Array(int[] arr1, int[] arr2) {
        int length1 = arr1.length;
        int length2 = arr2.length;

        int[] arr = new int[length1 + length2];
        // arr1的指针
        int j = 0;
        // arr2的指针
        int k = 0;
        // arr的指针
        int i = 0;
        while (j < length1 && k < length2) {
            if (arr1[j] <= arr2[k]) {
                arr[i] = arr1[j];
                i++;
                j++;
            } else {
                arr[i] = arr2[k];
                i++;
                k++;
            }
        }

        //把还没有进行合并的元素直接添加到新数组的后面
        while (j < length1) {
            arr[i] = arr1[j];
            i++;
            j++;
        }
        while (k < length2) {
            arr[i] = arr2[k];
            i++;
            k++;
        }

        return arr;
    }

    /**
     * 实现先将各个数组拼接到一起，然后再排序，从而实现有序排序
     * @param array
     * @return
     */
    public static int[] mergeArrays(int[][] array) {

        return null;
    }
}
